package com.zlk.algorithm.huawei.leetcode.dp.multidimensional;

/**
 * @program: algorithm
 * @ClassName Code56_minDistance
 * @description: 编辑距离
 * 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。
 * 你可以对一个单词进行如下三种操作：
 *
 * 插入一个字符
 * 删除一个字符
 * 替换一个字符
 * 示例 1：
 * 输入：word1 = "horse", word2 = "ros"
 * 输出：3
 * 解释：
 * horse -> rorse (将 'h' 替换为 'r')
 * rorse -> rose (删除 'r')
 * rose -> ros (删除 'e')
 * 示例 2：
 * 输入：word1 = "intention", word2 = "execution"
 * 输出：5
 * 解释：
 * intention -> inention (删除 't')
 * inention -> enention (将 'i' 替换为 'e')
 * enention -> exention (将 'n' 替换为 'x')
 * exention -> exection (将 'n' 替换为 'c')
 * exection -> execution (插入 'u')
 * @author: slfang
 * @create: 2025-01-16 16:25
 * @Version 1.0
 **/
public class Code56_minDistance {


    public int minDistance(String word1, String word2) {
        if(word1.length()<word2.length()){
            String temp = word2;
            word2 = word1;
            word1 = temp;
        }
        //保证dp数组小
        int n = word1.length();
        int m = word2.length();
        int[] dp = new int[m+1];
        for (int i = 0; i <=m; i++) {
            dp[i] = m-i;
        }
        for (int i = n-1; i >=0 ; i--) {
            int rightDown = dp[m];
            dp[m] = n-i;
            for (int j = m-1; j >=0 ; j--) {
                int temp = dp[j];
                int p1;
                if(word1.charAt(i)==word2.charAt(j)){
                    p1 = rightDown;
                }else{
                    p1 = rightDown+1;
                }
                int min = Math.min(dp[j]+1,dp[j+1]+1);
                dp[j] = Math.min(p1,min);
                rightDown = temp;
            }
        }
        return dp[0];
    }


    public int minDistanceDP(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();
        int[][] dp = new int[n+1][m+1];
        for (int i = 0; i <=n; i++) {
            for (int j = 0; j <=m; j++) {
                dp[i][j]=-1;
            }
        }
        return f1(word1,word2,0,0,dp);
    }

    // 可能性分析
    // s1 i
    // s2 j
    // 1、i位置等于j位置字符
    //    a:f(i+1,j+1)
    //    b:f(i+1,j)+1//j插入
    //    c:f(i,j+1)+1//i插入
    //
    //    d:f(i+1,j)+1//i删除
    //    f:f(i,j+1)+1//j删除
    //
    //2、i与j位置字符不相等
    //    a:f(i+1,j+1)+1    //i替换||j替换
    //    b:f(i+1,j)+1//j插入
    //    c:f(i,j+1)+1//i插入
    //
    //    d:f(i+1,j)+1//i删除
    //    f:f(i,j+1)+1//j删除
    //horse
    //ros
    private int f1(String s1,String s2, int i, int j,int[][] dp) {
        //base case
        if(dp[i][j]!=-1){
            return dp[i][j];
        }
        if(i==s1.length()&&j==s2.length()){
            dp[i][j]=0;
            return 0;
        }else if(i==s1.length()){
            if(j!=s2.length()){
                dp[i][j]=s2.length()-j;
                return s2.length()-j;
            }
        }else if(j==s2.length()){
            dp[i][j]=s1.length()-i;
            return s1.length()-i;
        }
        int p1;
        int p2;
        int p3;
//        int p4;
//        int p5;
        if(s1.charAt(i)==s2.charAt(j)){
            //匹配上当前的，找下一个
            p1 = f1(s1,s2,i+1,j+1,dp);
        }else{
            //替换
            p1 = f1(s1,s2,i+1,j+1,dp)+1;
        }
        p2 =  f1(s1,s2,i+1,j,dp)+1;
        p3 =  f1(s1,s2,i,j+1,dp)+1;
        dp[i][j]= Math.min(Math.min(p2,p3),p1);
        return dp[i][j];
    }


}
